package 二分;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/6 16:02
 */
public class lc1818绝对值差和 {


    /*
     你这种写法,是贪心, 但是错误的贪心, 无法得出贪心的正确性, 下面这个basecase 就挂掉了!
     nums1 :[1,28,21]
     nums2: [9,21,20]
     */
    public int solve(int nums1[], int nums2[]) {
        long ans = 0;
        int abs = 0,index = 0;
        if(Arrays.equals(nums1,nums2)){
            return 0;
        }
        for(int i = 0;i < nums1.length;i++){
            int temp = Math.abs(nums1[i] - nums2[i]);
            ans += temp;
            if(abs <= temp){
                index = i;
                abs = temp;
            }
            ans %= 1000_000_007;
        }
        Arrays.sort(nums1);
        // 直接二分 <= nums2[index]
        int l = 0, r = nums1.length - 1;
        while(l < r){
            int mid = l + r  + 1 >> 1;
            if(nums1[mid] > nums2[index]){
                r = mid - 1;
            }else{
                l = mid;
            }
        }
        // 边界情况要考虑一下
        int min = Math.abs(nums1[l] - nums2[index]);
        if(l != nums1.length - 1){
            min = Math.min(min, Math.abs(nums1[l + 1] - nums2[index]));
        }
        return (int) ans - abs + min;
    }



}
